The present invention relates to a program control apparatus in an information processing system, and in particular, to a control of an instruction buffer.
In order to increase the processing speed of an information processing system, an instruction buffer (described in pages 150-159 of the Computer Course 4 "Denshikeisanki no Hoshiki Sekkei (Computer System Design)" written by Kohzoh Sugashima, supervised by Hiroshi Inose, and published from Sangyo Shuppan) has been used. In an instruction buffer, a group of instructions which are to be used in a program currently being executed are previously read from a main memory and stored in a high-speed small capacity storage called an instruction buffer. Prefetching is used. As a result, the period of time necessary for a fetch operation of an instruction is reduced to improve the processing speed of the information processing system. Particularly, in a case where a sequence of instructions to be stored in the instruction buffer is to be iteratively executed in an instruction loop, a remarkable improvement is obtained in the second and subsequent iterations of the loop. In this case, since all instructions can be read out from the instruction buffer, the processing speed is efficiently increased. The operation above in which an instruction loop is completely loaded in the instruction buffer is called capture of an instruction loop.
The capture of the instruction loop is accomplished by sequentially replacing an old portion of the content of the instruction buffer with a new instructions read from the main memory for the next execution of the loop. An instruction replacement with a prefetch operation is carried out as a unit of instructions having a predetermined size or in a block of instructions. So long as the size of an instruction loop (the memory size of a group of instructions contained in the instruction loop) does not exceed the capacity of the instruction buffer, by sequentially replacing the old instructions not contained in the instruction loop with instructions contained in the loop, all instructions constituting the instruction loop are stored in the instruction buffer. The determination of an instruction block to be removed from the instruction buffer by replacement with a replacement algorithm has been commonly used. A method (First In First Out, FIFO) in which the replacement is conducted on an instruction block first stored in the instruction buffer as described above is used. Finally, a method (Least Recently Used, LRU) is used in which the instruction block least recently used is replaced.
In general instructions are arranged in the order of execution at consecutive addresses in the main storage. As a result, the prefetch operation is usually effected on a group of instructions at addresses subsequent to the address of an instruction currently being executed. This provision alone may achieve a considerable improvement. However, in a case where an instruction such as a conditional branch instruction, which may change the control flow exists in a sequence of instructions, there is a problem when the above method is employed. Namely, in the method described above, an instruction sequence to be executed when such a branch is not performed is previously prefetched. Each time the branch condition is satisfied and a branch is achieved, an instruction sequence at the branch target or destination is required to be read from the main memory. As a result, the improvement produced by the prefetch is greatly minimized. In order to satisfy this problem, a branch target instruction buffer has been utilized to prefetch therein a branch target instruction of the conditional branch instruction.